package org.example.algorithm.kmp;

/**
 * 字符串匹配问题：
 * 1) 有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串 str2="尚硅谷你尚硅你"
 * 2) 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
 * 3) 要求用最快的速度来完成匹配，请用Java代码实现
 * 字符串匹配算法：KMP算法——通过预处理模式串，构建一个部分匹配表（也称为next数组），然后在主串中进行匹配。
 *
 */
public class KMP {
    public static int[] computeNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;

        int j = -1;
        for (int i = 1; i < m; i++) {
            while (j >= 0 && pattern.charAt(i) != pattern.charAt(j + 1)) {
                j = next[j];
            }
            if (pattern.charAt(i) == pattern.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public static int kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] next = computeNext(pattern);

        int j = -1;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && text.charAt(i) != pattern.charAt(j + 1)) {
                j = next[j];
            }
            if (text.charAt(i) == pattern.charAt(j + 1)) {
                j++;
            }
            if (j == m - 1) {
                return i - j;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你";
        int index = kmpSearch(str1, str2);
        System.out.println("第一次出现的位置：" + index);
    }
}

